Douglas B. Lenat


Personal Data

Office address:         230 Margaret Jacks Hall
			Computer Science Dept.
                        Stanford University
                        Stanford, Ca. 94305

                        Telephone: 415-497-0304


Home address:      	1752 Selig Lane
                        Los Altos, Ca. 94022

                        Telephone: 415-965-1228


Born:                 	September 13, 1950, Philadelphia, Pa. 
                       	Citizenship: USA

Married:             	June 4, 1972
                       	Wife: Merle Ellyn Lenat
			Daughter: Nicolle Danielle Lenat (11/12/80)



Degrees Conferred

B.A. Mathematics, U. of Pa., June, 1972
B.A. Physics, U. of Pa., June, 1972
M.S. Applied Mathematics, U. of Pa., June, 1972
Ph.D. Computer Science, Stanford U., September, 1976



Scientific Investigations

1969: Natural Language interface to U. S. Navy data base question-answering 
system.

1970: Electron-electron scattering [as a research assistant to Dr. Walter 
Selove, Professor of experimental high-energy physics at the University 
of Pennsylvania].

1971: Acoustic Holography in Air at 40mHz. [Physics senior thesis].

1972: Computer-generated holograms of 3D projections of four-dimensional 
objects, and reconstruction by normal laser imaging.

1973: Simple automatic programming systems, using program template instantiation 
techniques: PW1, SEW, PUP. Described in [1].

1974: PUP6: an automatic programming system capable of generating a few 
ten-page long LISP concept-formation programs, from very constrained English 
dialogues. Described in [2,4].

1975: AM: a heuristic search program capable of performing simple math research. 
Described in [3,5,6].

1977: Architectures for rule-based computation systems. Discussed in [6,8,11]. 
See also [10].

1978-80: EURISKO: successor to AM.  Designed to (a) discover new heuristics, 
(b) develop journal-caliber mathematics,  and (c) build models of its users. 
See [9,19,21].

1979-80: Applying AI ideas to biology; specifically, work on the hypothesis
that evolution may by now proceed via plausible generation of mutations. [20]

1980: RLL: a Representation Language Language, a knowledge engineering tool 
to facilitate development of EURISKO. See [21,23].

1980: Theory of heuristics: inquiry into the nature of heuristic reasoning,
the source of power, the types of heuristics, a principled approach to
determining what attributes should be meaningful for heuristics.  See [19].



Published Papers
 

[1] Progress Report on Program-Understanding Systems, Memo AIM-240, CS Report 
STAN-CS-74-444, Artificial Intelligence Laboratory, Stanford University, 
August, 1974. Co-authored with Green, Waldinger, Barstow, Elshlager, McCune, 
Shaw, and Steinberg.

[2] Synthesis of Large Programs from Specific Dialogues,  Proceedings of 
the International Symposium on Proving and Improving Programs, IRIA, Le 
Chesnay, France, July, 1975.

[3] Duplication of Human Actions by an Interacting Community of Knowledge 
Modules, Proceedings of the Third International Congress of Cybernetics 
and Systems, Bucharest, Romania, August, 1975.

[4] BEINGS: Knowledge as Interacting Experts, Proceedings of the Fourth 
International Joint Conference on Artificial Intelligence, Tbilisi, USSR, 
September, 1975.

[5] AM: An Artificial Intelligence Approach to Discovery in Mathematics 
as Heuristic Search, Ph.D. Thesis, Stanford A. I. Lab Memo  Memo AIM-286, 
CS Report No. STAN-CS-76-570, and Heuristic Programming Project Report 
HPP-76-8, Stanford University, July, 1976.

[6] Designing a Rule System That Searches for Scientific Discoveries, (Lenat 
and Harris), invited paper for the conference in Honolulu, May, 1977; 
published in (Hayes-Roth and Waterman, eds.)   Proceedings of the Conference
on Pattern-Directed Inference, Academic Press, 1977. Also issued as a CMU 
technical report, April, 1977.

[7] Automated Theory Formation in Mathematics, Fifth IJCAI, Cambridge, Mass., 
August, 1977. 

[8] Less Than General Production System Architectures, (Lenat and J. 
McDermott,)  Fifth IJCAI, Cambridge, Mass., August, 1977.

[9] The Ubiquity of Discovery, the 1977  Computers and Thought Lecture 
(invited talk at the Fifth IJCAI). Preliminary version published in the 
proceedings of that conference; final version printed in the Journal of 
A.I.  Repeated as an invited talk at NCC (Anaheim, June, 1978).

[10]  Pattern Directed Inference Rules the Waves,  Journal of the AISB (Artificial 
Intelligence  Society of Britain), October, 1977, 8-12.  Reprinted in SIGART, 
1978.

[11] Rule Based Computation: Some Syntheses, (Hayes-Roth, Waterman, and 
Lenat), concluding chapter for (Hayes-Roth and Waterman, eds.)   Proceedings 
of the Conference on Pattern-Directed Inference, Academic Press, 1977.

[12]  Artificial Intelligence and Natural Statistics, invited paper at "Computer 
Science and Statistics: Eleventh Annual Symposium on the Interface", University 
of North Carolina at Raleigh, March 6, 1978.

[13] Unscripted interview on AI & Problem Solving, broadcast over the BBC, 
as part of the Open University's 32 week course on Cognitive Psychology. 
Taped at CMU on Feb. 22, 1978,  by Clive Holloway, Open University, Milton 
Keynes, England. 

[14]  On Astrophysics and Superhuman Performance, 
Journal of the Behavioral and Brain Sciences, Vol. 1, No. 1, 1978.

[15] On Automated Scientific Theory Formation: A Case Study Using the AM 
Program, in (Michie, ed.) Machine Intelligence 9, 1979.

[16]  Programs that Acquire Expert Knowledge: Two AI Approaches, (Davis 
& Lenat), McGraw Hill, 1980, 390pp.

[17] Machine Perception, Invited talk at the AAAS annual meeting, 
San Francisco, January, 1979.

[18] Cognitive Economy in Artificial Intelligence Systems,
Proc. Sixth IJCAI, Tokyo, 1979, 531-6. (Lenat, Hayes-Roth, and
Klahr)  Also issued as HPP-79-15, and submitted to J. Cognitive Science.

[19] Toward a Theory of Heuristics, HPP-80-26, CS Dept, Stanford, 1980.
Invited talk at the Bern conference on Heuristics.  Submitted to the Journal
of Artificial Intelligence.

[20] The Plausible Mutation of DNA, HPP-80-27, CS Dept, Stanford, 1980.
Submitted to Science.

[21] A Representation Language Language, Proc. First AAAI Conference, Stanford, 
1980. 

[22] Knowledge Engineering, an invited tutorial at the First AAAI Conf, Stanford,
1980.  Videotape publication and distribution. 

[23] Meta-Description and Modifiability in a Knowledge Representation
System, (Genesereth & Lenat)  HPP-80-18, CS Dept, Stanford, 1980.
To be submitted to the Journal of Artificial Intelligence.

[24] Building Expert Systems, (Hayes-Roth, Waterman, and Lenat, eds.), San
Diego, 1980 (to be published copyright 1981).




Interests


My main  research interest  is  Discovery: Can  we understand  how  people
synthesize new ideas?  I test my hypotheses by building computer  programs
which attempt to make discoveries.  Experimenting with the programs  leads
to criticism  and improvment  of the  original hypotheses,  to a  slightly
deeper understanding of human creativity.  Many issues must be dealt  with
in  constructing  such  programs:   how  to  represent  expert   knowledge
concretely, how to judge the worth of new discoveries, the difficulty (and
frequency) of discoveries  in various  human fields of  endeavor, when  to
reason symbolically and  inductively (and  slowly) versus  when to  reason
statistically  from  frequency   data  (and  hence   quickly),  what   the
architecture -- the design constraints -- of such reasoning programs might
be, etc.

The long-range goal of such research is "mental enhancement" of Man,  just
as medicine strives  toward biological  enhancement (e.g.,  immunization),
and  as   engineering   strives   toward   physical   enhancement   (e.g.,
automobiles).  In de-mystifying  the creative process,  we take the  first
halting steps toward a science of discovery, toward a science of Science.




Research at Stanford


During the past  two years at  Stanford, my research  has been  threefold.
(1) My earlier research led me to  conclude that new concepts can only  be
discovered in conjunction with  new specific heuristics, judgmental  rules
which are necessary to guide the discoverer effectively in the new  areas.
It seemed that this  capacity in turn demanded  some abilities to  develop
new representations for knowledge, in conjunction with new heuristics. One
major are of my research has been this relationship between representation
and discovery.  This  has led  to (i)  a new kind  of tool  for easily  --
automatically -- developing new  representation systems [21,23], and  (ii)
some insights into the nature of  heuristics, their origin and sources  of
power, the nature of the space of heuristics, etc.[19]

(2) Now armed with an experimental tool for investigating the discovery of
new heuristics, I have begun to build Eurisko, a program with expertise in
several specific  domains,  including  set theory,  number  theory,  graph
theory, geography, and biology, and some information in other fields  (oil
spills, games, programming).  Its task is to develop new concepts in those
fields, and find plausible conjectures connecting them.  This is much what
AM did.  In addition, I have become  convinced of the potency of proof  as
an instrument of discovery, and the Eurisko system has knowledge of  proof
types and techniques.  But the chief  advances of Eurisko over AM are  its
ability to find new heuristics and new kinds of attributes that are  worth
using; it  does  this  by generalizing  individual  experiences  (compiled
hindsight),  by   specializing  previously-known   generalities,  and   by
analogizing to concepts, heuristics, and slots of other fields, and to the
PATHS which were followed to produce them.

(3) The  results  of  experiments  such as  these,  and  earlier  ones  in
automatic programming,  led  to  a  radical  hypothesis  about  biological
evolution, namely  that long  before a  three billion  line DNA  "program"
would have evolved through random generation of mutations, nature may have
happened upon a much more efficacious -- yet scarcely more complicated  --
scheme for skewing mutations along  plausible paths, namely the method  of
heuristic search.  The hypothesis  is described in  [20]; there is  little
teleology in it: "plausible" means simply consistent with a record of  the
species' genetic history.

The initial focus in the coming three years will be on Eurisko:  extending
it, performing  experiments  on  it.  As  new  successes  and  limitations
appear, the "theory of heuristics" can  be furthered. To a lesser  degree,
the extension of the RLL  (representation language language) tool will  be
pursued; our major interest is  in its use for Eurisko,  not as an end  in
itself.


I  have  to  date  served  on  several  Ph.D  reading  committees,   orals
committees, and departmental committees.  My current PhD students are Russ
Greiner, Dave  Smith, and  Colleen  Crangle (special  program), and  I  am
co-advising Greg Cooper (special program).   I am supervising research  by
Dr. Jack Mostow (a research associate) and by several master's students.

Teaching has included 
1978/79:  CS206, CS224, CS229.
1979/80:  CS222, CS224, CS101, and CS301.
(1980/81:  CS222, CS224, CS301.)
The CS229  course was  a new  seminar on  heuristics and  problem-solving,
co-taught with  Professor  Polya.  CS301  and  CS101 were  co-taught  with
Professor Feigenbaum.  CS301 is a new course we introduced last Spring,  a
seminar on entering the computer science profession (teaching and  writing
skills,  choosing  a  thesis  topic,  funding,  consulting,  academia  vs.
industry, etc.)



External References


Robert Balzer, Information Sciences Institute, Los Angeles, Ca.
W. W. Bledsoe, Math Department, U. Texas at Austin
John Seely Brown, XEROX PARC, Palo Alto, Ca.
Randall Davis, Computer Sci. Dept.,  MIT, Cambridge, Mass.
Adrian de Groot, Amsterdam, Netherlands
Bernard Meltzer, Artificial Intelligence Dept., U. of Edinbugh, Scotland
Raj Reddy, Computer Science Dept., Carnegie-Mellon University, Pgh., Pa.
Pat Winston, Computer Science Dept., MIT, Cambridge, Mass.



Biography

Douglas B. Lenat was born in Philadelphia, and attended the University  of
Pennsylvania, where he  received B.A. dgrees  in math and  physics, and  a
M.S. in applied  math. His graduate  training was in  computer science  at
Stanford U.,  and  he  received his  Ph.D.  in  1976.  His  thesis  was  a
demonstration that certain kinds of "creative discoveries" in  mathematics
could be produced by a computer program (a theorem proposer, rather than a
theorem prover).   Lenat then  went to  Carnegie-Mellon University  as  an
assistant professor of computer science, and has recently taken that  same
position at Stanford University.  In  August, 1977, Lenat was awarded  the
biannual Computers & Thought Award by the International Joint Committee on
Artificial Intelligence.  His current research deals with the question  of
how to discover not merely mathematical conjectures, but informal rules of
thumb as  well.   Toward this  end,  Lenat  received an  ONR  contract  to
continue these investigations (through the summer of 1982).  Lenat's  wife
Merle is a marriage and family counselor.  On November 12, 1980, they  had
a baby girl.